문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 동적 계획법 (문단 편집) === 접근 === 동적 계획법의 개념과 구현에 대해 정확하게 짚고 넘어가기 위해 동적 계획법을 적용시킬 수 있는 예에 대해 알아보자. * f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 ) * f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0,n) = 1 위와 같이 정의된 함수에서 주어진 임의의 a,b에 대해 f(a,b)의 값을 효율적으로 구하고자 할 때 동적 계획법을 적용시킬 수 있다. 예를 들어 f(2,2)을 계산한다고 해보자. 이 경우 아래 그림과 같은 참조를 거치게 된다. [[파일:external/s21.postimg.org/tree.png]] 순서대로 계산횟수를 구해보면 f(2,2)를 구하기 위해 총 5번의 연산을 거쳐야한다. 이때 중복되는 부분 문제[* overlapping subproblems - 두 번 이상 계산되는 부분 문제]에 대한 답을 미리 계산해놓고 연산한다고 가정했을 때 계산횟수를 구해보면 f(2,2)를 구하기 위해 4번의 연산을 거쳐야한다. 이 경우 간단한 예라 중복되는 부분 문제가 f(1,1) 하나뿐이기 때문에 큰 속도의 이득을 볼 수 없지만 a, b의 값이 커질수록 속도 면에서 엄청난 이득을 볼 수 있다. 몇 가지 a, b 값에 대해 f(a, b)를 구하기 위한 연산 횟수를 나타낸 아래 표를 참고해보자. || {{{#fff (a,b)}}} || {{{#fff '''그냥 계산 시 연산 횟수'''}}} || {{{#fff '''동적 계획법 이용 시 연산 횟수'''}}} || || (2,2) || 5 || 4 || || (4,4) || 69 || 16 || || (6,8) || 3002 || 48 || || (10,10) || 184755 || 100 || 이 정도면 아마 대충 동적 계획법의 효율이 느껴질 것이다. 실제로 a, b가 1 증가할 때마다 연산 횟수는 기하급수적으로 증가하며, 이때 중복되는 부분 문제를 적절히 처리해줌으로써 높은 계산효율을 얻을 수 있는 것이다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기